package com.dyz.swordFingerOffer;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: daiyizheng
 * @date: 2021/5/30 11:37
 * @description:
 */
public class MovingCount13 {
    public static void main(String[] args) {
       int a =  new MovingCount13().MovingCount(1,2,1);
        System.out.println(a);
    }
    public int sum;
    public int MovingCount(int threshold, int rows, int cols){
        if(rows < 0 || cols < 0 ) {return -1;}
        sum = 0;
        boolean[][] vis = new boolean[rows][cols];
        dfs(0, 0, rows, cols, vis, threshold);
        return sum;
    }

    public int cul(int x, int y){
        int res = 0;
        while (x!=0){
            res += x%10;
            x /= 10;
        }
        while (y!=0){
            res += y%10;
            y /=10;
        }
        return res;
    }

    //深度优先
    public void dfs(int x, int y, int rows, int cols, boolean[][] vis, int threshold){
        //中止条件
        if(x<0 || x>=rows || y<0 || y>=cols || vis[x][y] || cul(x, y)>threshold){
            return;
        }
        vis[x][y]=true;
        //计算路径数
        sum++;
        //上下左右dfs
        dfs(x+1, y, rows, cols, vis, threshold);
        dfs(x-1, y, rows, cols, vis, threshold);
        dfs(x, y+1, rows, cols, vis, threshold);
        dfs(x, y-1, rows, cols, vis, threshold);
    }

    //广度优先 使用队列
    public int movingCount1(int thread, int rows, int cols){
        if(rows < 0 || cols < 0 ) {return -1;}
        sum = 0;
        boolean[][] vis = new boolean[rows][cols];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0,0});
        vis[0][0] = true;
        while (!queue.isEmpty()){
            int [] point = queue.poll();//pop 头节点
            int x = point[0];
            int y = point[1];

            //当已经确认机器人可以进入该坐标之后，才需要从这坐标向四个方向扩散
            if(cul(x, y)<=thread){
                sum++; //机器人可以进入该坐标，故计数加一，并从该坐标往四个方向扩散

                //四个方向（x+1, y）(x-1, y)(x, y+1)(x,y-1)
                //右
                if(x+1>=0 && x+1<rows && y>=0 && y<cols && !vis[(x+1)][y]){
                    queue.add(new int[]{x+1, y});
                    vis[(x+1)][y]=true;
                }
                //左
                if((x-1)>=0 && (x-1)<rows && y>=0 && y<cols && !vis[(x-1)][y]){
                    queue.add(new int[]{(x-1), y});
                    vis[(x-1)][y]=true;
                }

                //上
                if(x>=0 && x<rows && (y-1)>=0 && (y-1)<cols && !vis[x][(y-1)]){
                    queue.add(new int[]{x, (y-1)});
                    vis[x][(y-1)]=true;
                }

                //下
                if(x>=0 && x<rows && (y+1)>=0 && (y+1)<cols && !vis[x][(y+1)]){
                    queue.add(new int[]{x, (y+1)});
                    vis[x][(y+1)]=true;
                }
            }
        }
        return  sum;

    }



}
